#pragma once
#include <iostream>
#include <stdlib.h>
#include <vector>

namespace test
{

template<class V>
struct __hash_node
{
    V _val;
    __hash_node<V>* _next;

    __hash_node<V>(const V& val) : _val(val), _next(nullptr)
    {}
};

template<class K, class V, class HashFunc, class KeyOfVal>
class hash_table;

template<class K, class V, class HF, class KOV, class Ref, class Ptr>
struct __hash_iterator
{
    typedef __hash_node<V> node;
    typedef hash_table<K, V, HF, KOV> hash_table;
    typedef __hash_iterator<K, V, HF, KOV, V&, V*> iterator;
    typedef __hash_iterator<K, V, HF, KOV, Ref, Ptr> self;

    node* _node;
    const hash_table* _ht;


    __hash_iterator(node* n, const hash_table* ht) : _node(n), _ht(ht)
    {}

    __hash_iterator(const iterator& it) : _node(it._node), _ht(it._ht)
    {}

    Ref operator*()
    {
        return _node->_val;
    }

    Ptr operator->()
    {
        return &_node->_val;
    }

    bool operator==(const self& s)
    {
        return _node == s._node;
    }

    bool operator!=(const self& s)
    {
        return !this->operator==(s);
    }

    self& operator++()
    {
        if (_node->_next)
        {
            _node = _node->_next;
        }
        else
        {
            size_t hashi = _ht->_hash(_ht->_kov(_node->_val)) % _ht->_table.size();
            ++hashi;

            while (hashi < _ht->_table.size())
            {
                if (_ht->_table[hashi])
                {
                    _node = _ht->_table[hashi];
                    break;
                }
                ++hashi;
            }

            if (hashi == _ht->_table.size())
                _node = nullptr;
        }
        return *this;
    }
};

template<class K, class V, class HashFunc, class KeyOfVal>
class hash_table
{
public:
    typedef __hash_node<V> node;
    typedef __hash_iterator<K, V, HashFunc, KeyOfVal, V&, V*> iterator;
    typedef __hash_iterator<K, V, HashFunc, KeyOfVal, const V&, const V*> const_iterator;


    template<class K, class V, class HF, class KOV, class Ref, class Ptr>
    friend struct __hash_iterator;

public:
    const_iterator begin() const
    {
        for (auto cur : _table)
        {
            if (cur) return const_iterator(cur, this);
        }
        return end();
    }

    const_iterator end() const
    {
        return const_iterator(nullptr, this);
    }

    iterator begin()
    {
        for (auto cur : _table)
        {
            if (cur) return iterator(cur, this);
        }
        return end();
    }

    iterator end()
    {
        return iterator(nullptr, this);
    }

public:
    std::pair<iterator, bool> insert(const V& val)
    {
        auto pos = find(_kov(val));
        if (pos != end())
            return {pos, false};

        if (_table.empty() || _table.size() == _size)
        {
            size_t new_size = _table.empty() ? 10 : _table.size() * 2;
            std::vector<node*> new_table(new_size);

            for (auto& cur : _table)
            {
                while (cur)
                {
                    size_t hashi = _hash(_kov(cur->_val))%new_table.size();
                    node* next = cur->_next;

                    cur->_next = new_table[hashi];
                    new_table[hashi] = cur;

                    cur = next;
                }
            }

            _table.swap(new_table);
        }

        size_t hashi = _hash(_kov(val)) % _table.size();
        node* new_node = new node(val);

        new_node->_next = _table[hashi];
        _table[hashi] = new_node;
        ++_size;

        return {iterator(new_node, this), true};
    }

    iterator find(const K& key)
    {
        if (_table.empty())
            return end();

        size_t hashi = _hash(key) % _table.size();
        node* cur = _table[hashi];

        while (cur)
        {
            if (_hash(_kov(cur->_val)) == _hash(key))
                return iterator(cur, this);

            cur = cur->_next;
        }

        return end();
    }

    bool erase(const K& key)
    {
        if (_table.empty())
            return false;

        size_t hashi = _hash(key) % _table.size();
        node* cur = _table[hashi];
        node* prev = nullptr;

        while (cur)
        {
            if (_hash(_kov(cur->_val)) == _hash(key))
            {
                if (!prev)
                {
                    _table[hashi] = cur->_next;
                }
                else
                {
                    prev->_next = cur->_next;
                }
                delete cur;
                return true;
            }

            prev = cur;
            cur = cur->_next;
        }
        return false;
    }

private:
    std::vector<node*> _table;
    size_t _size = 0;

    KeyOfVal _kov;
    HashFunc _hash;
};

}